﻿#include <iostream>
#include <cstdio>
#include <string.h>
#include <iostream>
#include <fstream>
#include <windows.h>
using namespace std;
const int n = 28,N = 268435456;
int a[N];
int sum;
int init();
int way1(int);
int way2(int);
int way3(int);
int way4(int);
int getsum(int);
ofstream outfile;
LARGE_INTEGER t1,t2,tc;

int main()
{
	outfile.open("out1.txt", ios::out);
	int t = 1;
	init();
	for(int i = 0; i < n;i++)
	{
		t *= 2;
		outfile << t << ",";
		way1(t);
		way2(t);
		way3(t);
		way4(t);
	}
}

int init()
{
    for(int i = 0;i < N;i++)
	{
		a[i] = 0;
	}
}

int way1(int nn)
{
    QueryPerformanceFrequency(&tc);
    QueryPerformanceCounter(&t1);
    for(int o = 0;o < 100;o++)
    {
        sum = 0;
        for(int i = 0;i < nn;i++)
        {
            sum += a[i];
        }
    }
    QueryPerformanceCounter(&t2);
	outfile<<((t2.QuadPart - t1.QuadPart)*1.0 / tc.QuadPart)*10.0<<"ms"<<",";
	return 0;
}

int way2(int nn)
{
    QueryPerformanceFrequency(&tc);
    QueryPerformanceCounter(&t1);
    for(int o = 0;o < 100;o++)
    {
        sum = 0;
        int sum1 = 0,sum2 = 0;
        for(int i = 0;i < nn;i += 2)
        {
            sum1 += a[i];
            sum2 += a[i + 1];
        }
        sum = sum1 + sum2;
    }
    QueryPerformanceCounter(&t2);
	outfile<<((t2.QuadPart - t1.QuadPart)*1.0 / tc.QuadPart)*10.0<<"ms"<<",";
	return 0;
}

int way3(int nn)
{
    QueryPerformanceFrequency(&tc);
    QueryPerformanceCounter(&t1);
    for(int o = 0;o < 100;o++)
    {
        sum = 0;
        getsum(nn);
        init();
    }
    QueryPerformanceCounter(&t2);
	outfile<<((t2.QuadPart - t1.QuadPart)*1.0 / tc.QuadPart)*10.0<<"ms"<<",";
	return 0;
}

int getsum(int nn)
{
	if(nn == 1)
	{
		sum = a[0];
		return 0;
	}
	else
	{
		for(int i = 0;i < nn/2 ; i++)
		{
			a[i] += a[nn - i - 1];
		}
		nn = nn/2;
		getsum(nn);
	}
}

int way4(int nn)
{
    QueryPerformanceFrequency(&tc);
    QueryPerformanceCounter(&t1);
    for(int o = 0;o < 100;o++)
    {
        sum = 0;
        for(int m = nn;m > 1;m /= 2)
        {
            for(int i = 0;i < m/2;i++)
            {
                a[i] = a[i * 2] + a[i * 2 + 1];
            }
        }
        sum = a[0];
        init();
    }
    QueryPerformanceCounter(&t2);
	outfile<<((t2.QuadPart - t1.QuadPart)*1.0 / tc.QuadPart)*10.0<<"ms"<<endl;
	return 0;
}
